package leetcode_41_60;

public class firstMissingPositive_41 {
    /**
     * 时间复杂度为 O(n) 并且只使用常数级别额外空间
     * 那么各种排序方法不可用
     * 发现处理不了2，1   ，出现问题，这些整数是无序的
     * @param nums 未排序的整数数组
     * @return 其中没有出现的最小的正整数。
     */
    public int firstMissingPositive(int[] nums) {
        int minNum=1,
                a=0;           //minNum从1开始连续的整数集合的最后一个数  12345   ->  5
        for(int i=0;i<nums.length;i++){
            if( i != 0 && nums[i]<nums[i-1] && nums[i] > 0){  //大于0才参与比较
                minNum=nums[i];
            }
            if(nums[i]-a==1){  //如果出现从1开始连续的整数，记录下来尾值
                a=nums[i];
            }
        }
        if(minNum==1)
            return a+1;
        return Math.min(minNum, 1);
    }

    /**
     * 学习的思路，实在是妙啊
     * 遍历一次数组把大于等于1的和小于数组大小的值放到新数组对应位置，
     * 然后再遍历一次数组查当前下标是否和值对应，
     * 如果不对应那这个下标就是答案，
     * 否则遍历完都没出现那么答案就是数组长度加1。
     */
    public int firstMissingPositive2(int[] nums) {
        int [] newNums=new int[nums.length];
        for(int i=0;i<nums.length;i++){
            if(  nums[i] > 0 && nums[i] <= nums.length){
                newNums[nums[i]-1]=nums[i];                   //把大于等于1的和小于数组大小的值放到一个新数组对应位置
            }
        }
        for(int i=0;i<newNums.length;i++){
            if(newNums[i] != i+1){
                return i+1;
            }
        }
        return nums.length+1;
    }
}
